To find the most efficient path in a network, we must incorporate numerical costs (weights) and explicit travel direction.

  • Edges are assigned a numerical "cost" or weight, denoted as $w(u, v)$.
  • This cost represents real-world metrics like distance, time, latency, or fuel consumption.
  • The total cost of any path is calculated by summing the weights of all edges traversed.
  • Edges have a specific direction, indicated by an arrow, creating a Digraph.
  • An edge $(u, v)$ allows travel from $u$ to $v$, but the reverse path is not implied.
  • Directed graphs model dependencies, one-way systems, or flow where movement is restricted.
Adjacency List for Weighted, Directed Graph (Python)
1# G = {vertex: {neighbor: weight, ...}}
2
3weighted_graph = {
4    # A -> B (cost 5), A -> C (cost 2)
5    'A': {'B': 5, 'C': 2},
6    # B -> C (cost 1), B -> D (cost 4)
7    'B': {'C': 1, 'D': 4},
8    # C -> D (cost 6)
9    'C': {'D': 6},
10    'D': {}
11}